package binarytree

func insertIntoBST(root *TreeNode, val int) *TreeNode {
	if root == nil {
		root = new(TreeNode)
		root.Val = val
	} else {
		insert(root, val)
	}

	return root
}

func insert(root *TreeNode, val int) {
	if val > root.Val && root.Right == nil {
		temp := &TreeNode{
			Val: val,
		}
		root.Right = temp
		return
	} else if val > root.Val && root.Right != nil {
		insert(root.Right, val)
	}

	if val < root.Val && root.Left == nil {
		temp := &TreeNode{
			Val: val,
		}
		root.Left = temp
		return
	} else if val < root.Val && root.Left != nil {
		insert(root.Left, val)
	}
}
